package com.sicheng.datastruct.tree;

import lombok.AllArgsConstructor;
import lombok.Data;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/9/16 20:59
 */

@SuppressWarnings("all")
@Data
public class ReBuildBinaryTree {
    private Integer[] preOder;
    private Integer[] inOder;
    private Map<Integer, Node> indexsForInOrder;

    private HeroNode root;

    @Data
    @AllArgsConstructor
    static class Node {
        Integer index;
        Boolean exist;
    }

    public ReBuildBinaryTree(Integer[] preOder, Integer[] inOder) {
        this.preOder = preOder;
        this.inOder = inOder;
    }

    public HeroNode rebuild() {
        if (preOder == null || preOder.length == 0 || preOder.length != inOder.length)
            return null;


        root = new HeroNode(preOder[0]);

        if (inOder.length >= 2) {//当树的节点  >= 2
            indexsForInOrder = new HashMap<>();
            for (int i = 0; i < inOder.length; i++) {
                indexsForInOrder.put(inOder[i], new Node(i, false));
            }

            Node node = indexsForInOrder.get(root.getNo());
            node.exist = true;
            indexsForInOrder.put(root.getNo(), node);

            //开始递归 构造 树结构
            rebuild(root, indexsForInOrder, 0);
        }
        return root;
    }

    public void rebuild(HeroNode root, Map<Integer, Node> indexsForInOrder, int indexForPreorder) {

        if (indexForPreorder == preOder.length - 1)
            return;
        Integer RootIndexForInOrder = indexsForInOrder.get(preOder[indexForPreorder]).getIndex();
        //判断左子树是否存在
        if (RootIndexForInOrder > 0 && notInTree(inOder[RootIndexForInOrder - 1]) && notInTree(preOder[indexForPreorder + 1])) {//说明root有leftChild
            HeroNode leftChild = new HeroNode(preOder[indexForPreorder + 1]);
            //给当前root设置left
            root.setLeft(leftChild);

            Node node = indexsForInOrder.get(leftChild.getNo());
            node.exist = true;
            indexsForInOrder.put(leftChild.getNo(), node);
            //以left为递归的根继续
            rebuild(leftChild, indexsForInOrder, indexForPreorder + 1);
        }

        //右子树 是否存在
        if (RootIndexForInOrder < inOder.length - 1 && notInTree(inOder[RootIndexForInOrder + 1])) {
            HeroNode rightChild = null;
            if (!notInTree(preOder[indexForPreorder + 1])) {
                rightChild = new HeroNode(preOder[indexForPreorder + 2]);
                root.setRight(rightChild);

                Node node = indexsForInOrder.get(rightChild.getNo());
                node.exist = true;
                indexsForInOrder.put(rightChild.getNo(), node);
                rebuild(rightChild, indexsForInOrder, indexForPreorder + 2);
            } else {
                rightChild = new HeroNode(preOder[RootIndexForInOrder + 1]);
                root.setRight(rightChild);
                Node node = indexsForInOrder.get(rightChild.getNo());
                node.exist = true;
                indexsForInOrder.put(rightChild.getNo(), node);

                rebuild(rightChild, indexsForInOrder, indexForPreorder + 1);
            }
        }

    }

    private boolean notInTree(Integer id) {
        return !indexsForInOrder.get(id).exist;
    }

    public static int TreeDepth(HeroNode root) {
        return root == null ? 0 : 1 + Math.max(TreeDepth(root.getLeft()), TreeDepth(root.getRight()));
    }

    public static void main(String[] args) {
        ReBuildBinaryTree buildBinaryTreeTool =
                new ReBuildBinaryTree(new Integer[]{3, 9, 20, 15, 7}, new Integer[]{9, 3, 15, 20, 7});

        HeroNode root = buildBinaryTreeTool.rebuild();

        root.preOrder();

        System.out.println("===============");
        System.out.println(TreeDepth(root));
        System.out.println("======Inorder======");
        root.infixOrder();


    }


}
